﻿#include "seqlist.h"


//创造新节点
ListNode* LTBuyNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return 1;
	}
	newnode->next = newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

void LTInit(ListNode** pphead) //将链表初始化，所以传入的是二级指针
{
	*pphead = LTBuyNode(-1);  //简便方法
	return pphead;

	//void LTInit(LTNode** pphead)
//{
//	//*pphead = (LTNode*)malloc(sizeof(LTNode));
//	//if (*pphead == NULL)
//	//{
//	//	perror("malloc fail!");
//	//	exit(1);
//	//}
//	//(*pphead)->data = -1;
//	//(*pphead)->next = (*pphead)->prev = *pphead;
//	*pphead = LTBuyNode(-1);
//}

}

bool LTEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;  //返回
}

//销毁链表
void LTDestory(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur->next != phead)
	{
		/*pcur = pcur->next;
		free(pcur);*/
		ListNode* next = pcur->next;  //保留数据
		free(pcur);
		pcur = next;
	}
	//销毁头结点
	free(phead);
	phead = NULL;
}

//打印双链表  // 得跳过哨兵位
void SLTPrint(ListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL\n");
		return;
	}

	ListNode* pcur = phead->next; // 从第一个有效节点开始
	printf("哨兵 -> ");
	while (pcur != phead) // 循环链表，直到回到哨兵节点
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("哨兵\n"); // 回到哨兵节点，形成闭环
}


//尾插法：
void LTBushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = LTBuyNode(x); //创造了哨兵位

	newnode->prev = phead->prev;
	newnode->next = phead;
	//?
	phead->prev->next = newnode;//之前尾节点的下一个指针指向了newnode
	phead->prev = newnode;

}

//头插法：
void LTPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = LTBuyNode(x);


	/*newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next = newnode;*/

	if (phead->next == NULL) {  // 链表为空的情况
		newnode->next = phead;
		newnode->prev = phead;
		phead->prev = newnode;
		phead->next = newnode;
	}
	else {  // 链表不为空的情况
		newnode->next = phead->next;
		newnode->prev = phead;
		phead->next->prev = newnode;
		phead->next = newnode;
	}

}

//尾删法：
void LTPopBack(ListNode* phead)
{
	assert(phead);
	ListNode* p1 = phead->prev;
	p1->prev->next = phead;
	/*phead->next = p1->prev;*/
	phead->prev = p1->prev;
	free(p1);
	p1 = NULL;

	return phead;
}

//头删：
void LTPopFront(ListNode* phead)  // 删除的是哨兵位的下一个节点
{
	ListNode* p1 = phead->next;
	p1->prev->next = p1->next;
	p1->next->prev = phead;
	free(p1);
	p1 = NULL;
}

//查找元素
ListNode* LTFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* pcur = phead->next;
	while (pcur)
	{
		if (pcur->data == x)
		{
			//找到了
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在pos位置之后插⼊数据----在pos位置之前插入数据自行实现
void LTInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = LTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

	pos->next->prev = newnode;
	pos->next = newnode;


}
//删除pos位置的节点

void LTErase(ListNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}
